package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * b
 * dp
 * https://leetcode.cn/contest/sf-tech/problems/cINqyA/
 * 顺丰02. 小哥派件装载问题
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/10 14:54
 */
public class MinRemainingSpace {

    public static void main(String[] args) {
        MinRemainingSpace test = new MinRemainingSpace();

        // 1
        int[] arr = {8, 1, 12, 7, 9, 7};
        int v = 11;

        int i = test.minRemainingSpace(arr, v);
        System.out.println(i);
    }

    public int minRemainingSpace(int[] N, int V) {
        int length = N.length;
        boolean[] arr = new boolean[V + 1];
        arr[0] = true;
        for (int i = 1; i <= length; i++) {
            int num = N[i - 1];
            for (int j = V; j >= num; j--) {
                arr[j] = arr[j] || arr[j - num];
            }
        }
        for (int i = V; i >= 0; i--) {
            if (arr[i]) {
                return V - i;
            }
        }
        return 0;
    }

}
